Skip to main content

3-21 46. 把数字翻译成字符串

Date：2022-03-21 08:15:49

标签：

  • 动态规划

    从后向前分析

动态规划题目：

题目：46. 把数字翻译成字符串 ( 中等😕 )​

给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。

示例​

示例 1：

输入: 12258
输出: 5
解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"

分析​

image-20220321083022475

题解​

function translateNum(num: number): number {
  const numStr = num.toString()
  const len = numStr.length

  // 注意以下两者的区别
  // dp[i]表示从[0, i)翻译成字符串的总数，递推公式为：dp(i) = dp(i-1) + dp(i-2)(nums[(i-1), i] 可以翻译)
  // dp[i]表示从[0, i]翻译成字符串的总数，递推公式为：dp(i+1) = dp(i) + dp(i-1)(nums[(i), i+1] 可以翻译)
  const dp: number[] = new Array(len + 1)

  dp[0] = 1
  dp[1] = 1

  for (let i = 1; i < len; ++i) {
    dp[i + 1] = dp[i]

    const code = Number(numStr.slice(i - 1, i + 1))
    if (code >= 10 && code <= 25) {
      dp[i + 1] = dp[i] + dp[i - 1]
    }
  }

  return dp[len]
}

使用

function main() {
  const num = 12258

  console.log('[]:', translateNum(num))
}

main()

export {}

问题​

  • 为什么 dp[0] === 1 ?